Distances entre deux sommets - Exemple

On cherche la distance entre les sommets 3 et 7 dans le graphe non orienté suivant.

Sa matrice d’adjacence est  $A=\left(\begin{array}{ccccccccc}0& 1& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0& 1& 0\end{array}\right)$

$A^2=\left(\begin{array}{ccccccccc}1& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 4& 1& 1& 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 0& 0& 0& 1\\ 1& 1& 0& 2& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 4& 1& 0& 0& 1\\ 1& 0& 0& 1& 1& 3& 0& 1& 0\\ 0& 1& 0& 1& 0& 0& 1& 1& 0\\ 0& 1& 0& 1& 0& 1& 1& 2& 0\\ 0& 1& 1& 0& 1& 0& 0& 0& 2\end{array}\right)$

Son coefficient d'indices 3,7 est égal à 0, donc la distance entre les sommets 3 et 7 est supérieure à 2.

$A^3=\left(\begin{array}{ccccccccc}0& 4& 1& 1& 1& 0& 1& 1& 1\\ 4& 2& 0& 5& 7& 6& 1& 2& 1\\ 1& 0& 0& 1& 1& 3& 0& 1& 0\\ 1& 5& 1& 2& 5& 1& 1& 1& 2\\ 1& 7& 1& 5& 2& 2& 4& 5& 1\\ 0& 6& 3& 1& 2& 0& 1& 1& 4\\ 1& 1& 0& 1& 4& 1& 0& 0& 1\\ 1& 2& 1& 1& 5& 1& 0& 0& 3\\ 1& 1& 0& 2& 1& 4& 1& 3& 0\end{array}\right)$  

Son coefficient d'indices 3,7 est encore 0, donc la distance entre les sommets 3 et 7 est supérieure à 3.

$A^4=\left(\begin{array}{ccccccccc}4& 2& 0& 5& 7& 6& 1& 2& 1\\ 2& 22& 6& 9& 10& 3& 7& 8& 8\\ 0& 6& 3& 1& 2& 0& 1& 1& 4\\ 5& 9& 1& 10& 9& 8& 5& 7& 2\\ 7& 10& 2& 9& 21& 9& 2& 3& 7\\ 6& 3& 0& 8& 9& 13& 2& 6& 1\\ 1& 7& 1& 5& 2& 2& 4& 5& 1\\ 2& 8& 1& 7& 3& 6& 5& 8& 1\\ 1& 8& 4& 2& 7& 1& 1& 1& 7\end{array}\right)$

Son coefficient d'indices 3,7 est égal à $1\ne 0$ , donc la distance entre les sommets 3 et 7 est égale  à 4.

La chaîne à 4 arêtes qui relie les sommets 3 et 7 est : 3 - 4 - 2 - 5 - 7.

Remarque  

Ce n'est pas parce qu'on a trouvé une puissance de la matrice d'adjacence pour laquelle le coefficient  $(i,j)$ est nul qu'il est nul pour toutes les puissances précédentes. Pour trouver la distance entre deux sommets, il faut donc bien vérifier toutes les puissances successives.

Par exemple, ici, le coefficient  $(1,6)$  de  $A^3$  est nul. Il ne faudrait pas en conclure hâtivement que la distance entre ces deux sommets est supérieure à 3 ! En fait, le coefficient $(1,6)$  de  $A^2$  vaut  $1$ , il y a donc une chaîne de longueur 2 qui relie ces deux sommets (la chaîne 1 - 2 - 6). La distance entre les sommets 1 et 6 est 2.